from tools_algorithm import *


class Solution:
    def earliestSecondToMarkIndices(
        self, nums: List[int], changeIndices: List[int]
    ) -> int:

        n, m = len(nums), len(changeIndices)

        h = {}
        for i, v in enumerate(changeIndices):
            if v - 1 not in h:
                h[v - 1] = i

        def f(a):
            cnt = 0
            q = []
            nms = nums.copy()
            for i in range(a - 1, -1, -1):
                v = changeIndices[i] - 1
                if nms[v] < 2 or h[v] < i:
                    cnt += 1
                else:
                    if cnt == 0 and q and q[0][0] < nms[v]:
                        nms[q[0][1]] = q[0][0]
                        heapreplace(q, (nms[v], v))
                        nms[v] = -1
                        cnt += 1
                    elif cnt > 0:
                        heappush(q, (nms[v], v))
                        nms[v] = -1
                        cnt -= 1
                    else:
                        cnt += 1
            for v in nms:
                cnt -= v + 1
            return cnt >= 0

        ans = bisect_left(range(m + 1), True, key=lambda a: f(a))
        return ans if ans <= m else -1


class Solution:
    def earliestSecondToMarkIndices(
        self, nums: List[int], changeIndices: List[int]
    ) -> int:

        n, m = len(nums), len(changeIndices)

        h = {}
        # for i, v in enumerate(changeIndices):
        #     if v - 1 not in h:
        #         h[v - 1] = i
        for i in range(m - 1, -1, -1):
            h[changeIndices[i] - 1] = i
        total = n + sum(nums)

        def f(a):
            cnt = 0
            q = []
            sm = total
            for i in range(a - 1, -1, -1):
                v = changeIndices[i] - 1
                if nums[v] < 2 or h[v] < i:
                    cnt += 1
                else:
                    if not q and cnt == 0:
                        cnt += 1
                    elif cnt == 0 and q and q[0] < nums[v]:
                        sm += q[0] + 1
                        heapreplace(q, nums[v])
                        cnt += 1
                        sm -= nums[v] + 1
                    elif cnt > 0:
                        heappush(q, nums[v])
                        sm -= nums[v] + 1
                        cnt -= 1
                    else:
                        
            return cnt >= sm

        ans = bisect_left(range(m + 1), True, key=lambda a: f(a))
        return ans if ans <= m else -1


s = Solution()
print(7 == s.earliestSecondToMarkIndices([0, 0, 3, 0], [2, 2, 2, 2, 2, 2, 3, 1]))
print(-1 == s.earliestSecondToMarkIndices([1, 2, 3], [1, 2, 3]))
print(7 == s.earliestSecondToMarkIndices([0, 0, 1, 2], [1, 2, 1, 2, 1, 2, 1, 2]))
print(
    6
    == s.earliestSecondToMarkIndices(
        nums=[3, 2, 3], changeIndices=[1, 3, 2, 2, 2, 2, 3]
    )
)
print(
    10 == s.earliestSecondToMarkIndices([2, 1, 1, 2, 1], [1, 1, 5, 5, 5, 4, 4, 3, 2, 5])
)


# [3, 2, 3]
# [1, 3, 2, 2, 2, 2, 3]
# [0, 0, 1, 2]
# [1, 2, 1, 2, 1, 2, 1, 2]
# [1, 2, 3]
# [1, 2, 3]
# [4, 0, 1, 0]
# [4, 4, 4, 4, 2, 2, 1, 2, 4, 4, 1, 4, 2]
# [5, 3, 2, 0, 3, 5]
# [4, 3, 6, 5, 6, 5, 3, 6, 4, 1, 2, 3, 6, 1]
# [2, 1, 1, 2, 1]
# [1, 1, 5, 5, 5, 4, 4, 3, 2, 5]
# [2, 2]
# [2, 2, 1, 2]
# [0, 2]
# [1, 1, 2, 2, 1]
